# -*- coding: utf-8 -*-
# 给定一个可包含重复数字的序列，返回所有不重复的全排列

# 示例:
# 输入: [1,1,2]
# 输出:
# [
#   [1,1,2],
#   [1,2,1],
#   [2,1,1]
# ]

# # 解题思路同0046
# # 添加一次判定，每次选中元素的时候不选中重复元素
# class Solution(object):
#     def permuteUnique(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: List[List[int]]
#         """
#         def backtrack(index):
#             if index == n:
#                 rtn.append(nums[:]);
#                 return;

#             alrady = [];

#             for i in xrange(index, n):
#                 if nums[i] in alrady:
#                     continue;
#                 alrady.append(nums[i]);

#                 nums[index], nums[i] = nums[i], nums[index];
#                 backtrack(index + 1);
#                 nums[index], nums[i] = nums[i], nums[index];

#         n = len(nums);
#         rtn = [];
#         backtrack(0);
#         return rtn;









# 阅读算法找到更简单的去除重复元素的方法
# 
# 错误的思路，以及错误的地方
# 以[0,0,1,9]为例
# 1、对数组进行排序，然后选择元素时和前一个元素做比对，如果和前一个元素相同说明已经使用过了以此来去除重复
# 代码如下
# for i in xrange(index, len(nums)):
#     if i > 0 and nums[i] == nums[i - 1]:
#         continue;

#     nums[index], nums[i] = nums[i], nums[index];
#     backtrack(index + 1);
#     nums[index], nums[i] = nums[i], nums[index];
# 这个思路错误的地方在于交换，会改变已经排好序的数组
# eg: [0,0,1,9]
# 如果第一个数字选中9，则数组顺序变为
# [9,0,1,0]
# 很明显[0,1,0]并不是有序的，#1的方法判断重复就失败了
# 
# 
# 阅读他人算法中的解决方案
# 从一个有序数组中剔除一个元素，数组仍然是有序的
# 以此把剔除的元素 和 剩下的元素分为2个数组，即能使用#1来去除重复
# eg: [0,0,1,9]
# 如果第一个数字选中9，则数组变为
# [9] [0,0,1]
# [0,0,1]是有序的可以使用#1去除重复

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(nums, temp):
            if len(nums) == 1:
                rtn.append(temp + nums);
                return;

            for i in xrange(0, len(nums)):
                if i > 0 and nums[i] == nums[i - 1]:
                    continue;
                backtrack(nums[ : i] + nums[i + 1 :], temp + [nums[i]]);

        rtn = [];
        nums.sort();
        backtrack(nums, []);
        return rtn;

t = Solution();
print t.permuteUnique([3,3,0,3]);